This is an introductory video to Hashing which takes O(1) average time to search, insert or delete elements.
This track of the course covers the topic "Hashing".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Hashing.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This is an introductory video to Hashing which takes O(1) average time to search, insert or delete elements.
This video discusses various applications of Hashing.
This video starts discussing the concept of Hashing, beginning with the discussion of Direct Address Table.
Code:
This video discusses the working and various examples of Hash Functions.
This video discusses the problem of Collision that one can face in Hashing and various techniques on how to handle the collision problems.
This video talks about the first method of collision handling called Chaining.
Through this video, we will be learning how to implement chaining in case of occurrence of a collision.
C++ Code : https://ide.geeksforgeeks.org/WYbEzJo6Op
Java Code : https://ide.geeksforgeeks.org/KDAC6BGUrn
This video discusses Open Addressing which is another way of handling Collision in Hashing.
This video introduces us to the concept of double hashing where two hash functions are used to perform the hashing operation.
This video discusses the implementation of Open Addressing and how can it lead to avoiding of collision in Hashing.
Codes:
This video discusses the point of difference between Chaining vs Open Addressing.
This video discusses the Unordered set in CPP STL along with various functions involved in the unordered_set like:
This video discusses the unordered_map in C++ STL and how can it be implemented.
Code:
This video discusses the HashSet in Java along with few related library functions like,
Codes:
This video discusses the HashMap in Java
Codes:
This problem is an extension of the previously discussed problem of creating a subarray with zero-sum. This problem discusses the creation of similar subarray with a given input sum.
Codes:
Given an array, we need to find the longest subsequence that has consecutive elements. These consecutive elements may appear in any order in the subsequence.
Codes:
Given an array, one needs to Count Distinct Elements In Every Window of Size K.
Codes:
More than n/k Occurences
Codes:
More than n/k Occurences (O( nk) solution)
Codes:
Hashing is an improvement over Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as an index in a table called a hash table.
If slot hash(x) % S is full, then we try (hash(x) + 1) % SLet us consider a simple hash function as “key mod 7” and a sequence of keys as 50, 700, 76, 85, 92, 73, 101.
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
..................................................
..................................................
let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S
..................................................
..................................................
let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S
..................................................
..................................................
| S.No. | Seperate Chaining | Open Addressing |
| 1. | Chaining is Simpler to implement. | Open Addressing requires more computation. |
| 2. | In chaining, Hash table never fills up, we can always add more elements to chain. | In open addressing, table may become full. |
| 3. | Chaining is Less sensitive to the hash function or load factors. | Open addressing requires extra care for to avoid clustering and load factor. |
| 4. | Chaining is mostly used when it is unknown how many and how frequently keys may be inserted or deleted. | Open addressing is used when the frequency and number of keys is known. |
| 5. | Cache performance of chaining is not good as keys are stored using linked list. | Open addressing provides better cache performance as everything is stored in the same table. |
| 6. | Wastage of Space (Some Parts of hash table in chaining are never used). | In Open addressing, a slot can be used even if an input doesn't map to it. |
| 7. | Chaining uses extra space for links. | No links in Open addressing |
m = Number of slots in the hash table
n = Number of keys to be inserted in the hash table
Load factor α = n/m ( < 1 )
Expected time to search/insert/delete < 1/(1 - α)
So Search, Insert and Delete take (1/(1 - α)) time
The elements in the set are:
10 20 30 40 50 60
50 is present
set vs unordered_set
The elements in the unordered_set are:
10 50 30 60 40 20
50 is present
The map mp is :
KEY ELEMENT
1 40
2 30
3 60
4 20
5 50
6 50
7 10
The map umap is :
KEY ELEMENT
Contribute 30
GeeksforGeeks 10
Practice 20
unordered_map vs unordered_set
unordered_map vs map
map (like set) is an ordered sequence of unique keys whereas in the unordered_map key can be stored in any order, so unordered.{15=A computer, 3=Portal, 12=forGeeks, 1=Geeks}
{34=1, 3=1, 5=2, 10=3}
{one=practice.geeksforgeeks.org, two=code.geeksforgeeks.org, four=quiz.geeksforgeeks.org}
Getting value for key 'one': practice.geeksforgeeks.org
Size of the map: 3
Is map empty? false
Contains key 'two'? true
Contains value 'practice.geeksforgeeks.org'? true
delete element 'one': practice.geeksforgeeks.org
{two=code.geeksforgeeks.org, four=quiz.geeksforgeeks.org}
[South Africa, Australia, India]
HashSet contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India
Size of LinkedHashSet = 5
Original LinkedHashSet:[A, B, C, D, E]
Removing D from LinkedHashSet: true
Trying to Remove Z which is not present: false
Checking if A is present=true
Updated LinkedHashSet: [A, B, C, E]
TreeSet: [A, B, C]
TreeSet contains A or not:true
TreeSet after removing A:[B, C]
Iterating over TreeSet:
B
C
Asked In: Goldman Sachs
Asked In: Paytm
Asked In: Adobe
Asked In: Amazon

A | 10 |
B | 20 |
C | 30 |
D | 40 |